package com.example.demo.leetcode;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/02/29 10:34
 */
public class _42_接雨水 {
    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int[] height1 = {4, 2, 0, 3, 2, 5};
        int[] height2 = {0, 2, 0};
        int[] height3 = {8, 5, 4, 1, 8, 9, 3, 0, 0};
        int trap = trap2(height);
        System.out.println(trap);
    }

    /**
     * 方法一：
     * 思路：
     * 1.先找到数组中的最大值的下标index。如果有多个最大值，取第一个即可。
     * 2.以最大值下标index为分界线，把数组一分为二，左边和右边。
     * 3.在左边中再次找到最大值下标top，计算top和index之间能够接多少雨水。先计算两者间最大能接多少，然后再依次减去其中的数据。
     * 4.迭代左边的数据，直到完成遍历。
     * 5. 右边的同理。
     * <p>
     * 时间复杂度为：O(n^2)
     * 空间复杂度为: O(1)
     *
     * @param height 数组
     * @return {@link int}
     * @author WangYX
     * @date 2024/02/29 11:26
     */
    public static int trap(int[] height) {
        int start = 0;
        int end = height.length - 1;
        int index = findTop(height, start, end);

        int high = index;
        int num = 0;
        while (start < index) {
            int top = findTop(height, start, index - 1);
            num += num(height, top, index);
            index = top;
        }

        index = high;
        while (index < end) {
            int top = findTop(height, index + 1, end);
            num += num(height, index, top);
            index = top;
        }
        return num;
    }

    public static int findTop(int[] height, int start, int end) {
        if (start == end) {
            return start;
        }
        int index = 0;
        int max = -1;
        for (int i = start; i <= end; i++) {
            if (height[i] > max) {
                max = height[i];
                index = i;
            }
        }
        return index;
    }

    public static int num(int[] height, int start, int end) {
        int h1 = height[start];
        int h2 = height[end];
        int num = Math.min(h1, h2) * (end - start - 1);
        for (int i = start + 1; i <= end - 1; i++) {
            num -= height[i];
        }
        return num;
    }

    /**
     * 方法二：
     * 思路：
     * 从左到右遍历数组，依次遍历每个下标能接多少雨水，加在一起，即为结果。
     * <p>
     * 每个柱子能接的雨水，取决于当前柱子的左边最大值和当前柱子右边最大值的中较小的那个，再减去当前柱子。
     *
     * <p>
     * 时间复杂度为O(n^2)
     * 空间复杂度为O(1)
     *
     * @author WangYX
     * @date 2024/02/29 14:41
     * @version 1.0.0
     */
    public static int trap1(int[] height) {
        int num = 0;
        int length = height.length;
        for (int i = 1; i < length - 1; i++) {
            int value = height[i];
            int leftMax = 0;
            for (int j = 0; j < i; j++) {
                if (height[j] > leftMax) {
                    leftMax = height[j];
                }
            }
            int rightMax = 0;
            for (int j = i; j < length; j++) {
                if (height[j] > rightMax) {
                    rightMax = height[j];
                }
            }
            if (leftMax > value && rightMax > value) {
                num += Math.min(leftMax, rightMax) - value;
            }
        }
        return num;
    }

    /**
     * 方法三： 动态规划
     * 思路：
     * 方法三是方法二的进阶版。
     * 首先用两个数组：一个存放当前位置的左边最大值，一个存放当前位置右边的最大值。
     * <p>
     * 计算能接多少雨水时，直接从数组中取出左边最大值和右边最大值，然后进行比较取最小值，在减去当前的位置的值即可。
     * <p>
     * <p>
     * 时间复杂度：O(3n) = O(n)；
     * 空间复杂度：O(2n) = O(n)
     *
     * @author WangYX
     * @date 2024/02/29 15:00
     * @version 1.0.0
     */
    public static int trap2(int[] height) {

        int[] leftMaxArr = new int[height.length];
        int leftMax = 0;
        for (int i = 0; i < height.length; i++) {
            leftMaxArr[i] = leftMax;
            if (height[i] > leftMax) {
                leftMax = height[i];
            }
        }

        int[] rightMaxArr = new int[height.length];
        int rightMax = 0;
        for (int i = height.length - 1; i >= 0; i--) {
            rightMaxArr[i] = rightMax;
            if (height[i] > rightMax) {
                rightMax = height[i];
            }
        }

        int num = 0;
        for (int i = 0; i < height.length; i++) {
            if (leftMaxArr[i] > height[i] && rightMaxArr[i] > height[i]) {
                num += Math.min(leftMaxArr[i], rightMaxArr[i]) - height[i];
            }
        }
        return num;
    }


    /**
     * 方法四：单调栈
     *
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     *
     * @author WangYX
     * @date 2024/02/29 15:36
     * @version 1.0.0
     */
    public static int trap3(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                Integer top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int width = i - stack.peek() - 1;
                int high = Math.min(height[i], height[stack.peek()]) - height[top];
                num += width * high;
            }
            stack.push(i);
        }
        return num;
    }
}
